﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CSharp.Study.Algorithm
{
    public class 二分算法
    {
        private static int[] arr = new int[] { 1, 3, 4, 6, 7, 10, 12, 14, 15, 20 };
        public static void Go()
        {
            while (true)
            {
                var num = int.Parse(Console.ReadLine());
                Console.WriteLine(CheckIndex(num));
            }
        }

        /// <summary>
        /// 二分算法查数字在数组的索引
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        private static int CheckIndex(int num)
        {
            int left = 0, right = arr.Length - 1;
            while (left <= right)
            {
                double d = (left + right) / 2;
                int mid = (int)Math.Floor(d);
                if (arr[mid] < num)
                {
                    left = mid + 1;
                }
                else if (arr[mid] > num)
                {
                    right = mid - 1;
                }
                else
                {
                    return mid;
                }
            }
            return -1;
        }
    }
}
